﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace ParallelRuntimeLibrary.Internal
{

    /// <summary>
    /// Work-Stealing Queue (Queue have two end public, private)
    /// </summary>
    internal sealed class WorkStealingQueue
    {

        #region Variables
       
        private const int InitialSize = 32;

        private Task[] Array = new Task[InitialSize];

        private int Mask = InitialSize - 1;

        private volatile int HeadIndex = 0;
        private volatile int TailIndex = 0;

        private object ForeignLock = new object();

        #endregion

        /*///////////////////////////////////////////////////////////////////////////////////////////////*/

        #region Work-Stealing Queue methods

        internal void LocalPush(Task value)
        {
            int tail = TailIndex;
            if (tail < HeadIndex + Mask)
            {
                Array[tail & Mask] = value;
                TailIndex = tail + 1;
            }
            else
            {
                lock (ForeignLock)
                {
                    int head = HeadIndex;

                    int count = TailIndex - HeadIndex;

                    if (count >= Mask)
                    {

                        Task[] newArray = new Task[Array.Length << 1];

                        System.Array.Copy(Array, newArray, Array.Length);

                        Array = newArray;
                        HeadIndex = 0;
                        TailIndex = tail = count;
                        Mask = (Mask << 1) | 1;
                    }

                    Array[tail & Mask] = value;
                    TailIndex = tail + 1;
                }
            }
        }


        internal Task LocalPop()
        {
            int tail = TailIndex;
            if (HeadIndex >= tail) return null;

#pragma warning disable 0420

            tail -= 1;
            Interlocked.Exchange(ref TailIndex, tail);
            if (HeadIndex <= tail)
                return Array[tail & Mask];
            else
            {
                lock (ForeignLock)
                {
                    if (HeadIndex <= tail)
                    {
                        // Element still available. Take it.
                        return Array[tail & Mask];
                    }
                    else
                    {
                        // We lost the race, element was stolen, restore the tail.
                        TailIndex = tail + 1;
                        return null;
                    }
                }
            }
        }

        internal bool LocalPop(ref Task value)
        {
            int tail = TailIndex;
            if (HeadIndex >= tail)
                return false;

#pragma warning disable 0420

            tail -= 1;
            Interlocked.Exchange(ref TailIndex, tail);
            if (HeadIndex <= tail)
            {
                value = Array[tail & Mask];
                return true;
            }
            else
            {
                lock (ForeignLock)
                {
                    if (HeadIndex <= tail)
                    {
                        // Element still available. Take it.
                        value = Array[tail & Mask];
                        return true;
                    }
                    else
                    {
                        // We lost the race, element was stolen, restore the tail.
                        TailIndex = tail + 1;
                        return false;
                    }
                }
            }

        }

        /*/////////////////////////////////////////////////////////////////////////////*/

        internal bool TrySteal(ref Task value, int millisecondsTimeout)
        {
            bool taken = false;
            try
            {
                taken = Monitor.TryEnter(ForeignLock, millisecondsTimeout);
                if (taken)
                {
                    int head = HeadIndex;
                    Interlocked.Exchange(ref HeadIndex, head + 1);
                    if (head < TailIndex)
                    {
                        value = Array[head & Mask];
                        return true;
                    }
                    else
                    {
                        HeadIndex = head;
                        return false;
                    }
                }
            }
            finally
            {
                if (taken)
                    Monitor.Exit(ForeignLock);
            }
            return false;
        }

        internal Task Steal()
        {
            try
            {
                Monitor.Enter(ForeignLock);
                
                int head = HeadIndex;
                Interlocked.Exchange(ref HeadIndex, head + 1);
                if (head < TailIndex)
                    return Array[head & Mask];
                else
                {
                    HeadIndex = head;
                    return null;
                }
            }
            finally
            {
                Monitor.Exit(ForeignLock);
            }
        }

        #endregion
    }
}
